#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_VERTICES 10 // 最大顶点数

// 图结点结构（邻接表）
struct GraphNode
{
    int vertex;             // 顶点值
    struct GraphNode *next; // 指向下一个邻接结点
};

// 图结构
struct Graph
{
    int numVertices;             // 顶点数量
    struct GraphNode **adjLists; // 邻接表数组
    int *indegree;               // 每个顶点的入度数组
};

// 创建新结点
struct GraphNode *createNode(int v)
{
    struct GraphNode *newNode = (struct GraphNode *)malloc(sizeof(struct GraphNode));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

// 创建图
struct Graph *createGraph(int vertices)
{
    struct Graph *graph = (struct Graph *)malloc(sizeof(struct Graph));
    graph->numVertices = vertices;

    // 创建邻接表数组
    graph->adjLists = (struct GraphNode **)malloc(vertices * sizeof(struct GraphNode *));
    graph->indegree = (int *)malloc(vertices * sizeof(int));

    // 初始化邻接表和入度数组
    for (int i = 0; i < vertices; i++)
    {
        graph->adjLists[i] = NULL;
        graph->indegree[i] = 0;
    }

    return graph;
}

// 添加有向边（u -> v）
void addEdge(struct Graph *graph, int u, int v)
{
    // 创建新结点（v）
    struct GraphNode *newNode = createNode(v);

    // 将新结点添加到邻接表头部
    newNode->next = graph->adjLists[u];
    graph->adjLists[u] = newNode;

    // 增加目标顶点的入度
    graph->indegree[v]++;
}

// 拓扑排序
void topologicalSort(struct Graph *graph)
{
    printf("Topological Sort Order: ");

    // 创建队列（用于存储入度为0的顶点）
    int queue[MAX_VERTICES];
    int front = 0, rear = 0;

    // 1. 将所有入度为0的顶点加入队列
    for (int i = 0; i < graph->numVertices; i++)
    {
        if (graph->indegree[i] == 0)
        {
            queue[rear++] = i;
        }
    }

    // 记录已排序的顶点数
    int count = 0;

    // 2. 处理队列直到为空
    while (front < rear)
    {
        // 取出队列头部的顶点
        int u = queue[front++];
        printf("%d ", u); // 输出排序结果
        count++;

        // 3. 减少所有邻接顶点的入度
        struct GraphNode *temp = graph->adjLists[u];
        while (temp != NULL)
        {
            int v = temp->vertex;
            // 减少邻接顶点的入度
            graph->indegree[v]--;

            // 如果入度变为0，加入队列
            if (graph->indegree[v] == 0)
            {
                queue[rear++] = v;
            }

            temp = temp->next;
        }
    }

    // 4. 检查是否所有顶点都已排序
    if (count != graph->numVertices)
    {
        printf("\nERROR: Graph has a cycle! Not a DAG.\n");
    }
    else
    {
        printf("\n");
    }
}

// 打印图（邻接表形式）
void printGraph(struct Graph *graph)
{
    printf("\nGraph Representation (Adjacency List):\n");
    for (int i = 0; i < graph->numVertices; i++)
    {
        printf("Vertex %d: ", i);
        struct GraphNode *temp = graph->adjLists[i];
        while (temp != NULL)
        {
            printf("%d -> ", temp->vertex);
            temp = temp->next;
        }
        printf("NULL\n");
    }

    // 打印入度信息
    printf("\nIndegree Information:\n");
    for (int i = 0; i < graph->numVertices; i++)
    {
        printf("Vertex %d: indegree = %d\n", i, graph->indegree[i]);
    }
}

// 主函数测试
int main()
{
    // 创建有向无环图（6个顶点）
    struct Graph *graph = createGraph(6);

    // 添加有向边（构建DAG）
    addEdge(graph, 5, 2); // 5 -> 2
    addEdge(graph, 5, 0); // 5 -> 0
    addEdge(graph, 4, 0); // 4 -> 0
    addEdge(graph, 4, 1); // 4 -> 1
    addEdge(graph, 2, 3); // 2 -> 3
    addEdge(graph, 3, 1); // 3 -> 1

    // 打印图结构
    printGraph(graph);

    // 执行拓扑排序
    printf("\nPerforming topological sort:\n");
    topologicalSort(graph);

    return 0;
}